package 题目集.滑动窗口.ch02_不定长窗口;


import org.junit.Test;

/**
 * 给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 "" 。
 * https://leetcode.cn/problems/minimum-window-substring/description/
 */
public class ch03_最小覆盖子串 {
    /**
     * 思路：滑动窗口
     *      1.先统计t中每个字符的个数，用于表示每个字符需要被匹配几次。所有匹配的字符个数为sum
     *      2.用一个变量cnt表示已经匹配的个数。
     *          当前字符能匹配上t中的数字时，先看用于匹配的字符个数是否大于0，如果大于0则cnt++，如果小于0则cnt不变
     *          然后将该字符的匹配个数减一。
     *      3.窗口左边界移动时，查看左边界的字符是否在t中，如果在t中则将该字符的匹配个数加一，如果加一后大于0则cnt--。
     *      4.当cnt==sum时，表示当前窗口已经匹配上了t中的所有字符，记录下当前窗口的长度和起始位置。
     */
    static int[] need;   //存储t中每个字符的个数
//    static BitSet bitSet;     //因为0是有效数字，所以需要用bitSet标识t中的字符   //可以忽略
    static char[] charS;
    static char[] charT;

    public String minWindow(String s, String t) {
        need = new int[128];
//        bitSet = new BitSet(128);   //可以忽略
        charS = s.toCharArray();
        charT = t.toCharArray();
        int sum = 0;
        for (char c : charT) {
            sum++;
            need[c]++;
//            bitSet.set(c);
        }
        int cnt = 0;
        int start = 0, len = Integer.MAX_VALUE;
        //窗口左缩越容易不符合，窗口右扩越容易符合。
        //求解i在j结尾的情况下的最小长度
        for (int i = 0, j = 0; j < charS.length; j++) {
//            if (bitSet.get(charS[j])) {  //可以忽略，因为只有t中的才有可能是正数
                if (need[charS[j]]-- > 0) {
                    cnt++;
                }
//            }
            while (cnt == sum) {
                if (j - i + 1 < len) {
                    len = j - i + 1;
                    start = i;
                }
//                if (bitSet.get(charS[i])) {   //可以忽略，因为只有t中的才有可能是正数
                    need[charS[i]]++;
                    if (need[charS[i]] > 0) {
                        cnt--;
                    }
//                }
                i++;
            }
        }
        if (len == Integer.MAX_VALUE) {
            return "";
        }
        return s.substring(start, start + len);
    }

    @Test
    public void test() {
        System.out.println(minWindow("ADOBECODEBANC", "ABC"));
    }
}
